package com.xyj.week05;

import com.xyj.common.TreeNode;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 */
public class T6 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder,0,preorder.length-1,
                inorder,0,inorder.length-1);
    }

    /*
     *递归函数
     */
    public TreeNode build(int[] preorder, int preStart, int preEnd
            , int [] inorder, int inoStart, int inoEnd){
        // base case
        if(preStart>preEnd) {
            return null;
        }
        //根节点值
        int rootValue= preorder[preStart];
        //根据根节点在中序遍历找到其对应的索引和左子树、右子树
        int index =-1;
        for(int i=inoStart;i<=inoEnd;i++){
            if(inorder[i]==rootValue){
                index=i;
                break;
            }
        }
        //根节点
        TreeNode root =new TreeNode(rootValue);
        int leftSize=index-inoStart;
        root.left=build(preorder,preStart+1,preStart+leftSize,inorder,inoStart,index-1);
        root.right=build(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inoEnd);
        return root;
    }
}
